Well-posedness와 Ill-posedness 문제

짧은 설명

문제를 푼다는 것은 무엇인가?

저는 문제를 선형대수적으로 설명하고자 한다. 문제는 어떠한 입력을 넣었을 때, 답(해)가 나오는 규칙이다. 수식은 다음과 같다:

Ax = b 다음 식은 흔히 볼 수 있는 형태이다. 여기서 b는 관측값이고, A는 측정 또는 어떠한 물리 과정이고, x는 원인이라고 가정하자. 그러면 우리는 x라는 원인이 A라는 물리 과정이나 측정을 거쳐 b라는 관측값이 나왔다고 해석해볼 수 있다. 여기서 우리는 두 가지 용어를 얘기한다. 먼저, forward problem은 x \rightarrow b의 흐름을 가진 문제를 말한다. 원인을 입력으로 넣어 결과를 구하는 문제이다. 반대로, inverse problem은 x \leftarrow b의 흐름을 가진 문제이다. 관측값을 통해 원인을 구하는 문제이다.

여기서 inverse problem에는 중요한 점이 있다. 바로 관측값 b에 노이즈가 있다면, x가 크게 흔들릴 수 있다는 점이다. 예를 들어, 노이즈가 없는 깨끗한 관측값 b와 노이즈가 섞여있는 b + \epsilon이 있다고 했을 때 inverse problem을 풀면, A^{-1} b = 정확한 답이지만, A^{-1}(b + \epsilon) = 완전히 다른 답이 나올 수 있다.

Hadamard의 well-posedness 세 조건

Jacques Hadamard는 이러한 inverse problem 문제에서 나타나는 현상을 정형화하고자 1902년에 well-posed problem(잘 정의된 문제)를 정의한다. Hadamard는 well-posedness를 가지기 위해선 3가지 조건을 만족해야한다고 얘기한다. 1. 문제의 해가 존재(exist)해야 한다. 2. 문제의 해가 유일(unique)해야 한다. 3. 입력이 조금 바뀌면, 해도 조금 바뀌어야 한다. 즉, 연속성을 가져야 한다. \begin{aligned} &\text{existence: } \exists x \text{ such that } Ax=b \\ &\text{uniqueness: } x \text{ is unique} \\ &\text{stability: } y_n \to y \Rightarrow x_n \to x \end{aligned} Hadamard는 이 조건들 중에 하나라도 깨지면 ill-posed problem이라고 얘기한다.

하지만, 더 쉽게 진단 내릴 수 있는 방법은 determinant를 사용하는 것이다. 어떤 행렬 A가 determinant 값이 0이 아니라면 해당 행렬의 해는 존재하고 유일하다. 즉, well-posed를 만족한다. 예를 들어, A = \begin{bmatrix} 1 & 0 \\ 0 & 10^{-10} \end{bmatrix} 이면, \det(A)=10^{-10}\ne0 즉, 해당 matrix는 well-posed 이다.

조건수란?

조건수(condition number)는 입력이 조금 흔들렸을 때 해가 얼마나 크게 흔들리는지 나타내는 민감도이다. b에 작은 노이즈가 들어갔을 때 x가 얼마나 흔들리는지는 행렬 A의 조건수로 볼 수 있다. 조건수를 계산하는 공식은 대표적으로 두 가지가 있다: \kappa(A) = \|A\| \|A^{-1}\| 위 수식은 L2 norm을 통해서 계산하는 방법이다. \kappa_2(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)} 위 수식은 singular balue(\sigma)를 이용해서 계산하는 방법이다.

조건수가 큰 문제를 ill-conditioned problem이라 부른다. ill-conditioned는 보통 “풀 수는 있는데 작은 오차에 취약한 문제”이다. 그렇다면 well-posedness의 세번째 조건인 stability가 만족하지 않아서 ill-posed problem인 것과 뭐가 다른 것인지 의문이 생길 수 있다. 이를 정리하자면, ill-posed problem은 조건수 \kappa가 무한대 값(stability)인 경우이다. 반면에, ill-conditioned는 단순히, \kappa값이 큰 경우를 말한다. 앞서 얘기 했던 행렬 A = \begin{bmatrix} 1 & 0 \\ 0 & 10^{-10} \end{bmatrix} 을 다시 가져오자면, 해당 행렬은 well-posed 이지만 조건수를 계산해보면, \kappa_2(A)=10^{10} 이 나오기 때문에 ill-conditioned 이다.

inverse problem에서 ill-posedness가 자주 발생한다.

그 이유는 대표적으로 세 가지이다.

정보가 사라진다.

예를 들어, 카메라로 사진을 찍었을 때, 관측값은 2-dimensional matrix(= \mathbb{R}^{m \times n})가 나온다. 하지만, 실제 세계는 3차원으로 이루어져있기 때문에 z축에 의한 깊이도 존재하지만, 관측값으로는 해당 깊이를 역추적하기 어렵다. 즉, 깊이 정보가 사라진다.

Smoothing이랑 noise를 구분하지 못한다.

여기서 말하는 smoothing은 forward 과정이 정보를 부드럽게 만들어 세부 정보를 잃게 하는 현상을 뜻한다. 예를 들면, 이미지를 blur 처리하거나 모자이크 처리 하는 경우를 말할 수 있는데, blur 또는 모자이크 된 관측값을 다시 원상 복구 시키는 것은 noise와 blur 또는 모자이크 처리를 구분하기 어렵기 때문에 되돌리기 어렵다.

관측 데이터가 부족하다.

원인은 굉장히 고차원이지만, 관측값이 적은 경우를 말한다. 이미지의 깊이를 추정한다고 가정할 때, 관측값은 이미지 한장이지만, 원인이 되는 깊이 값은 여러개가 된다: A x_1 = b A x_2 = b A x_3 = b

Regularization

Regularization은 inverse problem에 부족한 정보를 인위적으로 보충하는 방법이다. 관측값만으로는 해가 하나로 정해지지 않거나, 해가 노이즈에 너무 민감할 수 있기 때문에, 해가 가져야 할 성질을 추가적인 조건으로 넣습니다. 가장 기본적인 형태는 다음과 같다:

\min_x \|Ax-b\|_2^2 + \lambda R(x)

첫 번째 항은 data fitting term이다.

\|Ax-b\|_2^2

즉, 해 x가 관측값 b를 얼마나 잘 설명하는지를 나타낸다. 두 번째 항은 regularization term이다:

R(x)

즉, 우리가 원하는 해의 성질을 나타낸다. 예를 들어 해가 너무 크지 않기를 원하면 다음처럼 regularization term을 설정해 추가적인 조건을 넣을 수 있다.

R(x)=\|x\|_2^2

이 경우 문제는 다음과 같습니다:

\min_x \|Ax-b\|_2^2 + \lambda \|x\|_2^2

이를 Tikhonov regularization 또는 ridge regularization이라고 부른다. 여기서 \lambda는 두 항 사이의 균형을 조절하는 파라미터이다. \lambda \approx 0이면 관측값을 최대한 잘 맞추는 것이 중요해지고, \lambda가 커질수록 해가 작고 안정적인 형태를 가지는 것이 중요해진다. 즉, regularization은 다음 trade-off를 조절한다.

\text{data fitting} \quad \leftrightarrow \quad \text{solution prior}

Tikhonov regularization의 해는 다음처럼 쓸 수 있다.

x_\lambda = (A^T A + \lambda I)^{-1}A^T b

여기서 A^T A에 \lambda I가 더해진 것이 핵심이다. 이 항은 작은 singular value 방향이 해를 과도하게 키우는 것을 억제한다.

SVD

SVD로 보면 이 효과가 더 잘 보인다. A를 다음처럼 분해한다고하자.

A = U \Sigma V^T

SVD에서 \Sigma는 singular value들을 대각성분으로 가지는 행렬이다.

\Sigma = \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_i \end{bmatrix}

inverse problem에서는 이 스케일링을 거꾸로 해야 하므로 \Sigma의 역행렬을 생각하게 된다.

\Sigma^{-1} = \begin{bmatrix} \frac{1}{\sigma_1} & 0 & \cdots & 0 \\ 0 & \frac{1}{\sigma_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \frac{1}{\sigma_i} \end{bmatrix}

즉, \sigma_i가 작을수록 그 방향의 성분은 크게 증폭된다. 반면 Tikhonov regularization에서는 이 항이 다음처럼 바뀐다.

\frac{\sigma_i}{\sigma_i^2 + \lambda}

이제 \sigma_i가 매우 작아도 값이 무한히 커지지 않는다. 즉, regularization은 불안정한 방향의 영향을 줄이는 필터처럼 작동한다.

이미지 복원

이미지 복원 문제에서는 R(x)를 다르게 선택할 수도 있다. 예를 들어 이미지가 너무 거칠지 않기를 원하면 인접한 픽셀 차이가 작아지도록 둘 수 있다.

R(x)=\|\nabla x\|_2^2

이 경우 regularization은 복원된 이미지가 관측값을 설명하면서도 너무 급격하게 변하지 않도록 만든다.